package org.apache.commons.graph.algorithms.shortestpath

import junit.framework.Assert
import org.apache.commons.graph.CommonsGraph.findShortestPath
import org.apache.commons.graph.Graph
import org.apache.commons.graph.MutableGraph
import org.apache.commons.graph.UndirectedGraph
import org.apache.commons.graph.weight.WeightedPath
import org.apache.commons.graph.algorithms.shortestpath.exception.PathNotFoundException
import org.apache.commons.graph.model.*
import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations
import org.junit.Test

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 */
class FloydWarshallTestCase {
    private fun findShortestPathAndVerify(weighted: Graph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>) {
        val mutable = weighted as MutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>

        // building Graph
        val one = BaseLabeledVertex("1")
        val two = BaseLabeledVertex("2")
        val three = BaseLabeledVertex("3")
        val four = BaseLabeledVertex("4")
        val five = BaseLabeledVertex("5")
        val six = BaseLabeledVertex("6")

        mutable.addVertex(one)
        mutable.addVertex(two)
        mutable.addVertex(three)
        mutable.addVertex(four)
        mutable.addVertex(five)
        mutable.addVertex(six)

        mutable.addEdge(one, BaseLabeledWeightedEdge("1 -> 6", 14.0), six)
        mutable.addEdge(one, BaseLabeledWeightedEdge("1 -> 3", 9.0), three)
        mutable.addEdge(one, BaseLabeledWeightedEdge("1 -> 2", 7.0), two)

        mutable.addEdge(two, BaseLabeledWeightedEdge("2 -> 3", 10.0), three)
        mutable.addEdge(two, BaseLabeledWeightedEdge("2 -> 4", 15.0), four)

        mutable.addEdge(three, BaseLabeledWeightedEdge("3 -> 6", 2.0), six)
        mutable.addEdge(three, BaseLabeledWeightedEdge("3 -> 4", 11.0), four)

        mutable.addEdge(four, BaseLabeledWeightedEdge("4 -> 5", 6.0), five)
        mutable.addEdge(six, BaseLabeledWeightedEdge("6 -> 5", 9.0), five)

        val p: AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            findShortestPath(weighted)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .applyingFloydWarshall(DoubleWeightBaseOperations)

        if (weighted is UndirectedGraph<*, *>) {
            // Verify shortestDistance
            Assert.assertEquals(11.0, p.getShortestDistance(one, six))

            Assert.assertEquals(11.0, p.getShortestDistance(six, one))

            Assert.assertEquals(6.0, p.getShortestDistance(four, five))
            Assert.assertEquals(6.0, p.getShortestDistance(five, four))

            Assert.assertEquals(20.0, p.getShortestDistance(one, five))
            Assert.assertEquals(20.0, p.getShortestDistance(five, one))

            // Verify shortest paths
            val wp = p.findShortestPath(one, six)

            // Expected
            val expected =
                InMemoryWeightedPath(one, six, DoubleWeightBaseOperations, BaseWeightedEdge())
            expected.addConnectionInTail(one, BaseLabeledWeightedEdge("1 -> 3", 9.0), three)
            expected.addConnectionInTail(three, BaseLabeledWeightedEdge("3 -> 6", 2.0), six)

            // Actual
            Assert.assertEquals(expected, wp)
        } else {
            Assert.assertEquals(11.0, p.getShortestDistance(one, six))

            Assert.assertEquals(6.0, p.getShortestDistance(four, five))

            Assert.assertEquals(20.0, p.getShortestDistance(one, five))
            org.junit.Assert.assertFalse(p.hasShortestDistance(five, one))

            var wp: WeightedPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>
            // Verify shortest paths
            try {
                wp = p.findShortestPath(five, one)
                org.junit.Assert.fail("Path from {5} to {1} doesn't exist")
            } catch (e: PathNotFoundException) {
                // wallow it
            }

            val expected =
                InMemoryWeightedPath(one, six, DoubleWeightBaseOperations, BaseWeightedEdge())
            expected.addConnectionInTail(one, BaseLabeledWeightedEdge("1 -> 3", 9.0), three)
            expected.addConnectionInTail(three, BaseLabeledWeightedEdge("3 -> 6", 2.0), six)

            // Actual
            wp = p.findShortestPath(one, six)
            Assert.assertEquals(expected, wp)
        }
    }

    @Test
    fun testDirectedShortestPath() {
        findShortestPathAndVerify(DirectedMutableGraph())
    }

    @Test(expected = PathNotFoundException::class)
    fun testNotConnectGraph() {
        val graph =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        graph.addVertex(a)
        graph.addVertex(b)

        // the actual weighted path
        val p: AllVertexPairsShortestPath<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            findShortestPath(graph)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .applyingFloydWarshall(DoubleWeightBaseOperations)

        p.findShortestPath(a, b)
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        // the actual weighted path
//        findShortestPath(null as Graph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>?)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .from(null)
//            .to(null)
//            .applyingDijkstra(DoubleWeightBaseOperations)
//    }

    @Test
    fun testUndirectedShortestPath() {
        findShortestPathAndVerify(UndirectedMutableGraph())
    }
}
